GATE IT 2005
Q11.
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree isQ12.
Let L be a regular language and M be a context-free language, both over the alphabet \Sigma. Let L^c and M^c denote the complements of L and M respectively. Which of the following statements about the language L^c\cup M^c is TRUE?Q14.
Two shared resources R_1 and R_2 are used by processes P_1 and P_2. Each process has a certain priority for accessing each resource. Let T_{ij} denote the priority of P_i for accessing R_j. A process P_i can snatch a resource R_k from process P_j if T_{ik} is greater than T_{jk}. Given the following : (I). T_{11} \gt T_{21} (II). T_{12} \gt T_{22} (III). T_{11} \lt T_{21} (IV). T_{12} \lt T_{22} Which of the following conditions ensures that P_1 and P_2 can never deadlock?Q15.
Consider the entities 'hotel room', and 'person' with a many to many relationship 'lodging' as shown below:If we wish to store information about the rent payment to be made by person (s) occupying different hotel rooms, then this information should appear as an attribute ofQ16.
Let f be a function from a set A to a set B, g a function from B to C, and h a function from A to C, such that h(a) = g(f(a)) for all a \in A. Which of the following statements is always true for all such functions f and g?Q17.
In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G isQ18.
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity. \begin{array}{|ll|ll|}\hline \text{1.} & \text{Bellman-Ford algorithm} & \text{A:} & \text{$O(m\log n)$} \\\hline \text{2.} & \text{Kruskal's algorithm} & \text{B:}& \text{$O(n^3)$} \\\hline \text{3.}& \text{Floyd-Warshall algorithm} & \text{C:} & \text{$O(nm)$} \\\hline \text{4.} & \text{Topological sorting} &\text{D:} & \text{$O(n+m)$} \\\hline \end{array}Q19.
The circuit shown below implements a 2-input NOR gate using two 2-4 MUX (control signal 1 selects the upper input). What are the values of signals x, y and z?Q20.
A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted?